package edu.cast.teseg.algoritmos.voraz;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author edgarin
 */
public class Dijkstra {
    
    
    private int[][] matrizAdj;
    private int[] cola;
    private String[] caminos;
    private int[] nodo_cumple;    
    private int porcentajeSi = 0;
    private int porcentajeNo = 0;
    
    
    public Dijkstra() {}
    
    
    //*** metodo que carga el origen en la cola de pesos de la matriz ***///
     public void iniciarOrigenes(int[] pesosVG,int origen){
        for (int i = 0; i < matrizAdj.length; i++) {
            pesosVG[i]=999;
        }
        pesosVG[origen]= 0;
        caminos[origen]=""+origen;            
    }
     
     //**** metodo que velirifica si es adjacente y si su peso en menor que el anterior ***//
     private void relajacion(int u, int[] pesosVG, int w[][], boolean[] visitadoVG){
         //******************** Extructira Optima **************************
                
        for (int i = 0; i < pesosVG.length; i++) {
            
           if(visitadoVG[i]==false){
               if(pesosVG[i] > (pesosVG[u] + w[u][i])){
                   pesosVG[i] = pesosVG[u] + w[u][i];
                  caminos[i] += caminos[u]+""+i+",";
               }
           }
        }
        //*****************************************************************
    }
     
     //***  metodo que ejecuta el altgoritmo dijkstra para cada vertice ***///
     public void ejecutaDijkstra(){
         int n = matrizAdj.length;
         nodo_cumple = new int[n];
         iniciarNodos();
         
         for (int totalV = 0; totalV < n; totalV++) {
            final boolean [] visitadoVG = new boolean [n];       
            iniciarOrigenes(cola,totalV);
            for (int i = 0; i <n; i++) {
                final int u = ExtraerMin.getExtraerMin(cola, visitadoVG);
                visitadoVG[u]=true;
                relajacion(u, cola, matrizAdj, visitadoVG);   
            }
            for (int i = 0; i < caminos.length; i++) {
                String camino = caminos[i].replaceAll(",","");
                int numNodos = camino.length();
                if(numNodos>6){
                    nodo_cumple[i] = 0;
                }                              
            }
             setCaminosVacios();
        }
         calcularPorcentaje();
    }

    public void setMatrizAdj(int[][] matrizAdj) {
        this.matrizAdj = matrizAdj;
    }

    public int[][] getMatrizAdj() {
        return matrizAdj;
    }    
    
    //*** metodo que asigna el tamaño de la matriz ***//
    public void configuraDijkstra(){
        caminos =  new  String[matrizAdj.length];
        cola = new int[matrizAdj.length];
        setCaminosVacios();
        
    }
    
     //*** metodo que promedia la cantidad de vertices que cumplen la teoria ***//
    private void calcularPorcentaje(){
        porcentajeSi = 0;
        for (int v = 0; v < matrizAdj.length; v++) {
            porcentajeSi += nodo_cumple[v];
        }
        porcentajeNo = matrizAdj.length-porcentajeSi;
        porcentajeNo = (porcentajeNo*100)/matrizAdj.length;
        porcentajeSi = (porcentajeSi*100)/matrizAdj.length;
        
    }
    
    public int getPorcentajeSi() { return porcentajeSi; }

    public int getPorcentajeNo() { return porcentajeNo; }
    
    
    //*** metodo que limpia los caminos ***//
    private void setCaminosVacios(){
        for (int i = 0; i < caminos.length; i++) {
            caminos[i]="";           
        }
    }
    
    //*** metodo que iniciar los nodos afirmando la teoria ***//
    private void iniciarNodos(){
        for (int i = 0; i < nodo_cumple.length; i++) {
            nodo_cumple[i]=1;            
        }
    }

    public void setPorcentajeNo(int porcentajeNo) {
        this.porcentajeNo = porcentajeNo;
    }

    public void setPorcentajeSi(int porcentajeSi) {
        this.porcentajeSi = porcentajeSi;
    }
    
}